// @algorithm @lc id=76 lang=cpp 
// @title minimum-window-substring


// @test("ADOBECODEBANC","ABC")="BANC"
// @test("a","a")="a"
// @test("a","aa")=""
class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> src, dst;
        for(auto &c : t) ++dst[c];
        function<bool()> IsWin = [&]()->bool{
            for(auto &[c,n] : dst)
                if(src[c] < n) return false;
            return true;
        };
        int left=0, right=0; // 可能包含 t 的滑动窗口
        int sub=-1, len=INT_MAX; // 最小子串
        for(int left=0,right=0; right<s.size(); right++){
            if(dst.count(s[right])) ++src[s[right]];
            while(IsWin() && left<=right){
                if(right-left+1<len){
                    len = right-left+1;
                    sub = left;
                }
                if(dst.count(s[left])) --src[s[left]];
                ++left;
            }
        }
        if(sub<0) return "";
        return s.substr(sub, len);
    }
};